package com.leetcode.algorithm.y22.m07.w4;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 347. 前 K 个高频元素
 * 
 * https://leetcode.cn/problems/top-k-frequent-elements/
 * 
 * @author jie.deng
 *
 */
class Question0347Solution01 {

	public int[] topKFrequent(int[] nums, int k) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int num : nums) {
			Integer cnt = map.get(num);
			if (cnt == null) {
				cnt = 0;
			}
			map.put(num, cnt + 1);
		}

		if (map.keySet().size() == k) {
			Iterator<Integer> iterator = map.keySet().iterator();
			int[] arr = new int[k];
			int idx = 0;
			while (idx < k) {
				arr[idx] = iterator.next().intValue();
				idx++;
			}
			return arr;
		}

		PriorityQueue<int[]> queue = new PriorityQueue<>((arr1, arr2) -> arr2[1] - arr1[1]);
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			queue.offer(new int[] { entry.getKey().intValue(), entry.getValue().intValue() });
		}

		int[] arr = new int[k];
		int idx = 0;
		while (idx < k) {
			arr[idx] = queue.poll()[0];
			idx++;
		}

		return arr;
	}

}